<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
       /* 
          时间是O(2^(m + n - 1)), 共有m+n - 1步，每一步都有两种可能性
          空间是O(m+n-1),递归调用栈的层数
       */
        var uniquePaths = function (m, n) {
            function dfs(x, y) {
                // 越界返回0
                if (x >= m || y >= n) return 0;
                
                // 到达终点
                if (x === m - 1 && y === n - 1) return 1;
                
                // 向右或向下搜索
                return dfs(x + 1, y) + dfs(x, y + 1);
            }
            return dfs(0, 0);
        };
        console.log(uniquePaths(3, 7));
        // // console.log(uniquePaths(3, 7));
        // console.log(uniquePaths(5, 4)); // 35
    </script>
</body>

</html>